package Algorithm;

import java.util.Arrays;

public class test5 {
    // 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数
    // 算法原理: 双指针
    public static boolean Triangle(int a, int b, int c) {
        return a + b > c;
    }

    // 解法二: 排序, 双指针优化
    // 时间复杂度: (nlog(n) * n)
    public static void main(String[] args) {
        int[] nums = {2, 2, 3, 4};
        // 排序
        Arrays.sort(nums);
        // count统计三角形的次数
        int count = 0;
        for (int i = nums.length - 1; i >= 2; i--) {
            // 2. 利用双指针快速统计出符合要求的三元组的个数,并固定每轮最大数
            int left = 0, right = i - 1, max = nums[i];
            // 3. 双指针循环遍历
            while (left < right) {
                if (nums[left] + nums[right] > max) {
                    count += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        System.out.println(count);
    }

    // 解法一: 暴力枚举
    // 时间复杂度: n^3 * nlog(n)
    public static void main1(String[] args) {
        int[] nums = {4, 3, 2, 2};
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (Triangle(nums[i], nums[j], nums[k])) {
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
    }
}
